package algorithm;

/**
 * 字符串大数加减乘法
 */
public class BigNum {
    /**
     * 大数相加 考虑负数
     * @param str1
     * @param str2
     * @return
     */
    public static String bigStrAdd(String str1, String str2){
        //验证字符串格式
        if(null == str1 || str1.isEmpty()){
            return str2;
        }
        if(null == str2 || str2.isEmpty()){
            return str1;
        }

        boolean isNagStr1 = str1.charAt(0) ==  '-';
        boolean isNagStr2 = str2.charAt(0) ==  '-';
        String format = "[1-9][0-9]*";
        boolean matchesStr1 = isNagStr1 ? str1.substring(1).matches(format) : str1.matches(format);
        boolean matchesStr2 = isNagStr1 ? str2.substring(1).matches(format) : str2.matches(format);
        if(!matchesStr1 || !matchesStr2) {
            throw new NumberFormatException("格式有误");
        }

        String resultStr = null;
        //都是负数
        if(isNagStr1 && isNagStr2){
            resultStr = '-' + add(str1.substring(1),str2.substring(1));
        }
        // 任一数是负数
        else if(isNagStr1 || isNagStr2){
            resultStr = subtract(str1,str2);
        }
        // 都是正数
        else{
            resultStr = add(str1,str2);
        }
        return resultStr;
    }

    /**
     * 相加
     * @param str1
     * @param str2
     * @return
     */
    private static String add(String str1, String str2) {
        StringBuilder sb = new StringBuilder();
        int len1 = str1.length() -1 , len2 = str2.length()-1;
        int carry = 0;
        while(len1 >=0 || len2 >=0 || carry != 0){
            int s1 = len1 >= 0 ? str1.charAt(len1--) - '0' : 0;
            int s2 = len2 >= 0 ? str2.charAt(len2--) - '0' : 0;
            int sum = s1 + s2 + carry;
            carry = sum / 10;
            sb.append(sum % 10);
        }
        return sb.reverse().toString();
    }

    /**
     * 大数减法
     *
     * @param str1
     * @param str2
     * @return
     */
    public static String subtract(String str1, String str2) {
        boolean compare = compare(str1, str2);
        // 始终保持大数减小数 str1 > str2
        if (compare) {
            String temp = str2;
            str2 = str1;
            str1 = temp;
        }
        int len1 = str1.length() - 1, len2 = str2.length() - 1;
        StringBuilder sb = new StringBuilder();
        // 减法借位
        int borrow = 0;
        while (len1 >= 0 || len2 >= 0) {
            if (len1 == 0 && str1.charAt(0) == '-' || (len2 == 0 && str2.charAt(0) == '-')) {
                break;
            }
            int num1 = len1 >= 0 ? str1.charAt(len1--) - '0' : 0;
            int num2 = len2 >= 0 ? str2.charAt(len2--) - '0' : 0;
            int sub = num1 - num2 - borrow;
            if (sub < 0) {
                borrow = 1;
                sub += 10;
            }
            sb.append(sub);
        }
        sb.reverse();
        int index = 0;
        // 去掉字符前缀的0
        while (index < sb.length() && sb.charAt(index) == '0') {
            index++;
        }
        if (index == sb.length()) {
            return "0";
        }
        if (str1.charAt(0) == '-') {
            return '-' + sb.substring(index);
        }
        return sb.substring(index);
    }

    /**
     * 比较字符串大小
     *
     * @param str1
     * @param str2
     * @return
     */
    private static boolean compare(String str1, String str2) {
        String s1 = str1;
        String s2 = str2;
        // 去掉负号比较
        s1 = s1.replace("-", "");
        s2 = s2.replace("-", "");
        if (s1.length() > s2.length()) {
            return false;
        } else if (s1.length() < s2.length()) {
            return true;
        } else {
            // 长度相等 直接用compareTo比较
            return s1.compareTo(s2) < 0;
        }
    }

    public static String mul(String num1, String num2) {
        return "";
    }

    public static void main(String[] args) {
        String str1 = "351";
        String str2 = "3172";
        System.out.println(BigNum.bigStrAdd(str1, str2));
        System.out.println(BigNum.subtract(str1, str2));
    }
}
